package lc2;
import java.util.*;
import org.junit.*;

public class Ex1610 {
    
    class Solution {

        public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
            //1. 计算所有点和人的连线的角度【相对于x轴】
            List<Double> angs = new ArrayList<>();
            int x = location.get(0), y = location.get(1);

            //记录与location点相同的point数量
            int same = 0;  
            double pi = Math.PI;

            for (List<Integer> point : points) {
                int x1 = point.get(0), y1 = point.get(1);
                if (x1 == x && y1 == y) {
                    same++;
                } else {
                    double ag = Math.atan2(y - y1, x - x1);
                    if (ag < 0) {
                        ag += 2 * pi;
                    }
                    angs.add(ag);
                }
            }
            
            //2. 对所有点进行排序
            Collections.sort(angs);

            //扩展一倍的点
            int n = angs.size();

            /**
             * 1. 处理([-pi, 0]，即第三四象限的负数；)
             * 2. 处理(第四象限到第一象限的值)
             * 3. 尽管会将某些差值重复计算，但是并不会改变max。
             */
            for (int i = 0; i < n; i++) {
                angs.add(angs.get(i) + 2 * pi);
            }

            //3. 滑动窗口进行最大窗口统计
            int max = 0;
            int lo = 0, hi = 0;
            n *= 2;

            //获取angel的角度值
            double limit = (double)angle / 360 * 2 * pi;

            while (hi < n) {
                double start = angs.get(lo);
                while (hi < n) {
                    double d = angs.get(hi) - start;
                    if (d > limit) {
                        break;
                    }
                    hi++;
                }
                max = Math.max(hi - lo, max);
                
                if (hi == n) {
                    break;
                }

                lo++;
            }

            return max + same;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        List<List<Integer>> list = new ArrayList<>(){{
            add(Arrays.asList(0, 0));
            add(Arrays.asList(0, 2));
        }};

        System.out.println(s.visiblePoints(list, 90, Arrays.asList(1, 1)));
    }

}
